package Tree;

import _4lists.src.stack.LinkedListStack;

import java.util.LinkedList;

public class noRecrsion_bianli {
    //建立一个二叉树
    /*
     *                   1
     *             2           3
     *         4     null    5    6
     * */
    public static void main(String[] args) {
        TreeNode root = new TreeNode(
                new TreeNode(new TreeNode(4), 2, null),
                1,
                new TreeNode(new TreeNode(5), 3, new TreeNode(6))
        );
        preOrder(root);
        System.out.println();
        inOrder(root);
        System.out.println();
        postOrder(root);
    }

    //前序遍历
    /*前序遍历的特点
     * 1.先访问根节点
     * 2.然后返回左子树
     * 2.最后访问右子树
     * 访问结果：1，2，4，3，5，6*/
    static void preOrder(TreeNode root) {
        TreeNode dummy = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        while (dummy != null||!stack.isEmpty()) {//确保全部遍历
            if (dummy != null) {
                System.out.print(dummy.val+" ");
                stack.push(dummy);//入栈，记住来时的路，方便回去遍历右子树
                dummy = dummy.left;
            }else {
                TreeNode pop = stack.pop();
                dummy = pop.right;//沿着右边走
            }
        }
    }

    //中续遍历
    /*中序遍历的特点
     * 1.先访问左子树
     * 2.然后返回根节点
     * 2.最后访问右子树
     * 访问结果：4，2，1，5，3，6*/
    static void inOrder(TreeNode root) {
        TreeNode dummy = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        while (dummy != null||!stack.isEmpty()) {//确保全部遍历
            if (dummy != null) {
                stack.push(dummy);//入栈，记住来时的路，方便回去遍历右子树
                dummy = dummy.left;
            }else {
                TreeNode pop = stack.pop();
                System.out.print(pop.val+" ");
                dummy = pop.right;//沿着右边走
            }
        }
    }

    //后续遍历
    /*前序遍历的特点
     * 1.先访问左子树
     * 2.然后返回右子树
     * 2.最后访问根节点
     * 访问结果：4，2，5，6，3，1*/
    static void postOrder(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode curr = root;
        TreeNode pop = null;//后续添加的中间变量值

        while (!stack.isEmpty() || curr != null) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                //先拿到栈顶元素，不能直接去pop，因为根节点但是最后输出的
                TreeNode peek = stack.peek();
                //需要先进行左右节点的判断，左边在上面的if已经为空，只需要对右边的进行判断
                //分为等于null和不等于null(输出元素的值的条件就是该节点的左右两边均为null，这是和前两者不同的地方)
                if (peek.right == null || peek.right == pop) {//多的地方
                    pop = stack.pop();
                    System.out.print(pop.val+" ");
                } else {
                    curr = peek.right;
                }
            }
        }
    }
}
